Preprint No.
A-01-13
Ehrhard Behrends, Bernd Schmidt
Can one determine a graph by counting walks?
Abstract:
Let $G$ be a rooted graph with root $x_{0}$ and
denote, for any positive integer $n$, by $a_{n}$ the number of walks of
length $n$ which start at $x_{0}$. Is it possible to identify $G$ up
to isomorphism from the sequence $(a_{n})$?
This problem can be thought of as a disrete variant of Kac' famous
``Can you hear the shape of a drum?''. In the present paper it
is analysed in detail for a certain rather simple class of rooted trees.
Keywords: tree, identification problem, random walk,
drum
Mathematics Subject Classification (MSC2000): Primary 05C05. Secondary 05C60, 60J10.
Language: ENG
Available: Pr-A-01-13.ps
Contact: Ehrhard Behrends, Freie Universität Berlin, Fachbereich Mathematik und Informatik, Arnimallee 2-6, D-14195 Berlin, Germany (behrends@math.fu-berlin.de)
[Home Page] - [Up] - [Search] - [Help] - Created: 20010703 -